package BinaryTree;

public class MaxBinarySearchTree {

    /**
     * 求二叉树的最大距离
     * curr当前节点
     * 1. 跟curr无关， max（左子树的最大距离，右子树的最大距离）
     * 2. 跟curr有关， 左子树高度+右子树高度+1
     * **/

    public Info getSizeOfBST(TreeNode node) {
        if (node == null) return null;
        Info left = getSizeOfBST(node.left);
        Info right = getSizeOfBST(node.right);
        int min = node.val;
        int max = node.val;
        if (left != null) {
            min = Math.min(min, left.min);
            max = Math.max(max, left.max);
        }
        if (right != null) {
            min = Math.min(min, right.min);
            max = Math.max(max, right.max);
        }

        boolean isBST = (left == null ? true : left.max <= node.val) && (right == null ? true : right.min >= node.val)
                && (left == null ? true : left.isAllBST) && (right == null ? true : right.isAllBST);

        int maxSize = isBST ? (left == null ? 0 : left.maxSubBSTSize) + (right == null ? 0 : right.maxSubBSTSize) + 1
                : Math.max(left == null ? 0 : left.maxSubBSTSize, right == null ? 0 : right.maxSubBSTSize);

        return new Info(isBST, maxSize, max, min);

    }


    class Info {
        public int max;
        public int min;
        public boolean isAllBST;
        public int maxSubBSTSize;

        public Info(boolean is, int size, int ma, int mi) {
            isAllBST = is;
            maxSubBSTSize = size;
            max = ma;
            min = mi;
        }
    }


}
